package com.cyy.test_t_6_;

/**
 * @Description 剑指Offer t_62 - 二叉搜索树的第k个结点
 * 题目描述：
 * 给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8）中，
 * 按结点数值大小顺序第三小结点的值为4。
 *
 * 算法思想：
 *  二叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。
 *  所以，按照中序遍历顺序找到第k个结点就是结果。
 * @Author Crystal
 * @Date 2019/7/18 22:07
 * @Version 1.0
 **/
public class t_62 {
    /**
     * 定义二叉树
     */
    private static class TreeNode {
        private int val;
        private TreeNode left;
        private TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

    }

    private static int index = 0; //计数器
    public static TreeNode KthNode(TreeNode pRoot, int k) {
        if(k <= 0) return null;

        if(pRoot != null) {
            TreeNode node = KthNode(pRoot.left,k);
            if(node != null){
                return node;
            }
            index ++;
            if(index == k){
                return pRoot;
            }
            node = KthNode(pRoot.right,k);
            if(node != null){
                return node;
            }
        }
        return null;
    }

    private static void assemble(TreeNode node,
                                 TreeNode left,
                                 TreeNode right) {
        node.left = left;
        node.right = right;
    }

    public static void main(String[] args) {
        test01();
    }

    //                            8
    //                  6                  10
    //             5        7         9          11
    public static void test01() {
        TreeNode n1 = new TreeNode(8); // 12
        TreeNode n2 = new TreeNode(6); // 10
        TreeNode n3 = new TreeNode(10); // 14
        TreeNode n4 = new TreeNode(5); // 9
        TreeNode n5 = new TreeNode(7); // 11
        TreeNode n6 = new TreeNode(9); // 13
        TreeNode n7 = new TreeNode(11); // 15
        assemble(n1, n2, n3);
        assemble(n2, n4, n5);
        assemble(n3, n6, n7);

        System.out.println(KthNode(n1,1).val);

    }

}